#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

int Find_boundary(int* p, int sz, int target, int left,int right ,int flag)
{
    int mid = 0;
    int result = 0;
    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (*(p + mid) == target)//记录该数出现的位置
        {
            result = mid;
            if (flag)//求第一次出现的位置
            {
                right = mid - 1;
            }
            else//求最后一次出现的位置
            {
                left = mid + 1;
            }
        }
        else if (*(p + mid) > target)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return result;
}

int countOccurrences(int nums[], int sz, int target)
{
    int firstboundary = Find_boundary(nums, sz, target,0 ,sz - 1,1);//求该数在数组第一次出现的位置
    int endboundary = Find_boundary(nums, sz, target, 0,sz - 1,0);//求该数在数组最后一次出现的位置
    return endboundary - firstboundary + 1;
}

int main()
{
    int nums[] = { 1,1,1,1,2,2,3,3,4,4,5 };
    int sz = sizeof(nums) / sizeof(nums[0]);
    int target = 0;
    scanf("%d", &target);
    int ret = countOccurrences(nums, sz, target);
    printf("%d在数组出现的次数为：%d", target, ret);
    return 0;
}
































// 返回数字第一次出现的位置或最后一次出现的位置
//int binarySearch(int* nums, int target, int left, int right, int findFirst) {
//    int result = -1;
//    while (left <= right)
//    {
//        int mid = left + (right - left) / 2;
//
//        if (nums[mid] == target)
//        {
//            result = mid; // 找到目标数字，记录当前位置
//
//            if (findFirst)
//                right = mid - 1; // 继续在左半部分查找第一次出现的位置
//            else
//                left = mid + 1; // 继续在右半部分查找最后一次出现的位置
//        }
//        else if (nums[mid] < target)
//        {
//            left = mid + 1;
//        }
//        else
//        {
//            right = mid - 1;
//        }
//    }
//
//    return result;
//}
//
//// 计算数字在升序数组中出现的次数
//int countOccurrences(int nums[], int size, int target)
//{
//    // 使用二分查找找到数字第一次出现的位置和最后一次出现的位置
//    int firstIndex = binarySearch(nums, target, 0, size - 1, 1);
//    int lastIndex = binarySearch(nums, target, 0, size - 1, 0);
//
//    // 计算数字出现的次数
//    int count = lastIndex - firstIndex + 1;
//
//    return count;
//}
//
//int main()
//{
//    int nums[] = { 1, 1, 1, 4, 4, 4, 4, 5 };
//    int target = 4;
//    int size = sizeof(nums) / sizeof(nums[0]);
//
//    int count = countOccurrences(nums, size, target);
//
//    printf("数字 %d 在数组中出现的次数为: %d\n", target, count);
//
//    return 0;
//}